package com.yequan.leetcode.heap.topKFrequent_347;

import java.util.*;

/**
 * //给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
 * //
 * // 示例 1:
 * //
 * // 输入: nums = [1,1,1,2,2,3], k = 2
 * //输出: [1,2]
 * //
 * //
 * // 示例 2:
 * //
 * // 输入: nums = [1], k = 1
 * //输出: [1]
 * //
 * // 说明：
 * //
 * //
 * // 你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
 * // 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
 * //
 * // Related Topics 堆 哈希表
 *
 * @author : Administrator
 * @date : 2020/3/28
 */
public class TopKFrequent {

    public static void main(String[] args) {
        int[] nums = new int[]{1, 1, 1, 2, 2, 3};
        TopKFrequent topKFrequent = new TopKFrequent();
        List<Integer> res = topKFrequent.topKFrequent(nums, 2);
        res.forEach(num -> System.out.println(num));
    }

    /**
     * 小顶堆:
     * 1.先统计数组元素出现的次数
     * 2.将所有出现的次数存放进大顶堆中,取出前k个
     *
     * @param nums
     * @param k
     * @return
     */
    public List<Integer> topKFrequent(int[] nums, int k) {
        List<Integer> res = new ArrayList<>();
        Map<Integer, Integer> count = new HashMap<>();
        Queue<Integer> heap = new PriorityQueue<>((n1, n2) -> count.get(n1) - count.get(n2));
        for (int num : nums) {
            count.put(num, count.getOrDefault(num, 0) + 1);
        }
        for (Integer num : count.keySet()) {
            heap.add(num);
            if (heap.size() > k) {
                heap.poll();
            }
        }
        for (int i = 0; i < k; i++) {
            res.add(heap.poll());
        }
        return res;
    }

}
